import java.util.ArrayList;
import java.util.List;

/**
 * 199. 二叉树的右视图
 * https://leetcode-cn.com/problems/binary-tree-right-side-view/
 */
public class Solutions_199 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.right = new TreeNode(5);
        root.right = new TreeNode(3);
        root.right.right = new TreeNode(4);

        List<Integer> result = rightSideView(root);
        System.out.println(result);
    }

    public static List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();;
        dfs(root, 0, res);
        return res;
    }

    public static void dfs(TreeNode root, int level, List<Integer> res) {
        if (root == null) {
            return;
        }
        if (level == res.size()) {
            // 保证 root.val 为树中每一层的最右节点
            res.add(root.val);
        }
        level ++;
        // 子树递归顺序：先右再左
        dfs(root.right, level, res);
        dfs(root.left, level, res);
    }
}
